package everydayGrade.t4;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @Author: Siantar
 * @Date: 2023-10-21-20:15
 * @Description: 1.0
 */
public class T2316 {
    public long countPairs(int n, int[][] edges) {
        List<Integer>[] lists = new List[n];
        for (int i = 0; i < n; i++) {
            lists[i] = new ArrayList<Integer>();
        }
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            lists[x].add(y);
            lists[y].add(x);
        }
        boolean[] bs = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        int f = 0, left = 0;
        long res = 0;
        while (f < n) {
            int t = 0;
            while (f < n && bs[f]) f++;
            if (f == n) break;
            stack.push(f);
            System.out.println("push"+f);
            bs[f] = true;
            while (!stack.isEmpty()) {
                int p = stack.pop();
                t++;
                System.out.println(t+"  "+p);
                for (int next : lists[p]) {
                    if (!bs[next]) {
                        stack.push(next);
                        System.out.println("push"+next);
                        bs[next] = true;
                    }
                }
            }
            System.out.println(t);
            res += (long) left * t;
            left += t;
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(countPairs(3, new int[][]{{0, 1}, {0, 2}, {1, 2}}));
        ;
    }
}
